home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / list.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  11.7 KB  |  269 lines
  1. {\magonebf 3.7 Linear Lists  (list) }
  2.  
  3. \decl list E
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $L$ of the parameterized data type \name\ is a sequence of items
  8. ($list\_item$). Each item in $L$ contains an element of data type $E$, called 
  9. the element type of $L$. The number of items in $L$ is called the length of $L$.
  10. If $L$ has length zero it is called the empty list. In the sequel $<x>$ is used 
  11. to denote a list item containing the element $x$ and $L[i]$ is used to denote 
  12. the contents of list item $i$ in $L$.
  13.  
  14.  
  15. \bigskip
  16. {\bf 2. Creation}
  17.  
  18.  
  19. \create L {}
  20.    
  21. creates  an instance \var\ of type \name\ and initializes it to the empty list.
  22.  
  23.  
  24. \bigskip
  25. {\bf 3. Operations }
  26.  
  27. \+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
  28.  
  29. {\bf a) Access Operations}
  30. \medskip
  31. \+\op int        length {}                
  32.                                {returns the length of $L$.}
  33. \smallskip
  34. \+\op int        size {}                
  35.                                {returns $L$.length().}
  36. \smallskip
  37. \+\op bool       empty {}                 
  38.                                {returns true if $L$ is empty, false otherwise.}
  39. \smallskip
  40. \+\op list\_item first {}                 
  41.                                {returns the first item of $L$.}
  42. \smallskip
  43. \+\op list\_item last {}                  
  44.                                {returns the last item of $L$.}
  45. \smallskip
  46. \+\op list\_item succ {list\_item\ it}        
  47.                                 {returns the successor item of item $it$, nil}
  48. \+\nop                          {if $it = L$.last().}
  49. \+\nop                          {\precond $it$ is an item in $L$.}
  50. \smallskip
  51. \+\op list\_item pred {list\_item\ it}        
  52.                                {returns the predecessor item of item $it$, nil}
  53. \+\nop                         {if $it = L$.first().}
  54. \+\nop                         {\precond $it$ is an item in $L$.}
  55. \smallskip
  56. \+\op list\_item cyclic\_succ {list\_item\ it} 
  57.                     {returns the cyclic successor of item $it$, i.e.,}
  58. \+\nop              {$L$.first() if $it = L$.last(), $L$.succ($it$) otherwise.}
  59. \smallskip
  60. \+\op list\_item cyclic\_pred {list\_item\ it} 
  61.                     {returns the cyclic predecessor of item $it$, i.e,}
  62. \+\nop              {$L$.last() if $it = L$.first(), $L$.pred($it$) otherwise.}
  63. \smallskip
  64. \+\op list\_item search {E\ x}                  
  65.                            {returns the first item of $L$ that contains $x$,}
  66. \+\nop                     {nil if $x$ is not an element of $L$}
  67. \smallskip
  68. \+\op E          contents {list\_item\ it}    
  69.                                    {returns the contents $L[it]$ of item $it$ }
  70. \+\nop                             {\precond $it$ is an item in $L$.}
  71. \smallskip
  72. \+\op E          inf {list\_item\ it}    
  73.                                    {returns $L$.contents($it$).}
  74. \smallskip
  75. \+\op E          head {}                  
  76.                           {returns the first element of $L$, i.e. the contents}
  77. \+\nop                    {of $L$.first().} 
  78. \+\nop                    {\precond $L$ is not empty.}
  79. \smallskip
  80. \+\op E          tail {}                  
  81.                           {returns the last element of $L$, i.e. the contents}
  82. \+\nop                    { of $L$.last().}
  83. \+\nop                    {\precond $L$ is not empty.}
  84. \smallskip
  85. \+\op int        rank {E\ x}
  86.                           {returns the rank of $x$ in $L$, i.e. its first}
  87. \+\nop                    {position in $L$ as an integer from [1\dots $|L|$]}
  88. \+\nop                    {(0 if $x$ is not in $L$). }
  89.  
  90.  
  91. \medskip
  92. {\bf b) Update Operations}
  93. \medskip
  94. \+\op list\_item insert {E\ x, list\_item\ it,\ direction\ dir=after}    {}
  95. \+\nop                     {inserts a new item $<x>$ after (if $dir=after$)}
  96. \+\nop                     {or before (if $dir=before$) item $it$ into $L$ and}
  97. \+\nop                     {returns it. \precond $it$ is an item in $L$.}
  98. \smallskip
  99. \+\op list\_item push {E\ x}          
  100.                              {adds a new item $<x>$ at the front of $L$ and}
  101. \+\nop                       {returns it ( $L$.insert($x,L$.first$(),before$) )}
  102. \smallskip
  103. \+\op list\_item append {E\ x}        
  104.                               {appends a new item $<x>$ to $L$ and returns}
  105. \+\nop                        {it ( $L$.insert($x,L$.last$(),after$) )}
  106. \smallskip
  107. \+\op E          del\_item {list\_item\ it}      
  108.                           {deletes the item $it$ from $L$ and returns its }
  109. \+\nop                    {contents $L[it]$.}
  110. \+\nop                    {\precond $it$ is an item in $L$.}
  111. \smallskip
  112. \+\op E          pop {}                   
  113.                           {deletes the first item from $L$ and returns its }
  114. \+\nop                    {contents.}
  115. \+\nop                    {\precond $L$ is not empty.}
  116. \smallskip
  117. \+\op E          Pop {}                   
  118.                           {deletes the last item from $L$ and returns its }
  119. \+\nop                    {contents.}
  120. \+\nop                    {\precond $L$ is not empty.}
  121. \smallskip
  122. \+\op void       assign {list\_item\ it,\ E\ x}
  123.                            {makes $x$ the contents of item $it$.}
  124. \+\nop                     {\precond $it$ is an item in $L$.}
  125. \smallskip
  126. \+\op void       conc {list\&\ L1}          
  127.                               {appends list $L1$ to list $L$ and makes $L1$ the}
  128. \+\nop                        {empty list}
  129. \smallskip
  130. \+\op void       split {list\_item\ it, list\&\ L1,\ L2}           {}
  131. \+\nop                {splits $L$ at item $it$ into lists $L1$ and $L2$}
  132. \+\nop                {and makes $L$ the empty list. More precisely,}
  133. \+\nop                {if $L = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then}
  134. \+\nop                {$L1 = x_1,\dots,x_{k-1}$ and $L2 = it,x_{k+1},\dots,x_n$}
  135. \+\nop                {\precond $it$ is an item in $L$. }
  136. \smallskip
  137. \+\op void       apply {void\ (*f)(E\&)}  
  138.                               {for all items $<x>$ in $L$ function $f$ is}
  139. \+\nop                        {called with argument $x$ (passed by reference).}
  140. \smallskip
  141. \+\op void       sort {int\ (*cmp)(E\&,E\&)}   
  142.                 {sorts the items of $L$ using the ordering defined}
  143. \+\nop          {by the compare function $cmp : E\times E \longrightarrow int$,}
  144. \+\nop          {\phantom{with $cmp(a,b)$} $ < 0$,  if $a < b$ }
  145. \+\nop          {with $cmp(a,b)$           $ = 0$,  if $a = b$ }
  146. \+\nop          {\phantom{with $cmp(a,b)$} $ < 0$,  if $a > b$ }
  147. \+\nop          {More precisely, if $L = (x_1,\dots,x_n)$ before the sort}
  148. \+\nop          {then $L = (x_{\pi(1)},\dots,x_{\pi(n)})$ for some permutation}
  149. \+\nop          {$\pi$ of $[1..n]$ and $cmp(L[x_j],L[x_{j+1}]) \le 0$ for}
  150. \+\nop          {$1\le j<n$ after the sort.}
  151.  
  152. \smallskip
  153. \+\op void       bucket\_sort {int\ i,\ int\ j,\ int\ (*f)(E\&)}  {}
  154. \+\nop            {sorts the items of $L$ using bucket sort, }
  155. \+\nop            {where $f : E \longrightarrow int$ with $f(x) \in [i..j]$ for}
  156. \+\nop            {all elements $x$ of $L$. The sort is stable, }
  157. \+\nop            {i.e., if $f(x)=f(y)$ and $<x>$ is before $<y>$ in}
  158. \+\nop            {$L$ then $<x>$ is before $<y>$ after the sort.}
  159. \smallskip
  160. \+\op void       permute {}                    
  161.                                 {the items of $L$ are randomly permuted.}
  162. \smallskip
  163. \+\op void       clear {}                      
  164.                                     {makes $L$ the empty list }
  165.  
  166. \bigskip
  167. {\bf c) Input and Output}
  168. \smallskip
  169. \+\op void       read {istream\ I,\ char\ delim = '\backslash n'}     {}
  170. \+\nop                      {reads a sequence of objects of type $E$ terminated}
  171. \+\nop                      {by the delimiter $delim$ from the input stream $I$}
  172. \+\nop                      {using the overloaded $Read$ function (section 1.5)}
  173. \+\nop                      {$L$ is made a list of appropriate length and the}
  174. \+\nop                      {sequence is stored in $L$.}
  175. \smallskip
  176. \+\op void       read {char\ delim = '\backslash n'}
  177.                             {Calls $L$.read($cin$, $delim$) to read $L$ from}
  178. \+\nop                      {the standard input stream $cin$.}
  179. \smallskip
  180. \+\op void       read {string\ s,\ char\ delim = '\backslash n'}     {}
  181. \+\nop                      {As above, but uses string $s$ as a prompt.}
  182. \smallskip
  183. \+\op void       print {ostream\ O,\ char\ space = '\ '}    {} 
  184. \+\nop                      {Prints the contents of list $L$ to the output}
  185. \+\nop                      {stream $O$ using the overload $Print$ function}
  186. \+\nop                      {(cf.~section 1.5) to print each element. The}
  187. \+\nop                      {elements are separated by the character $space$.}
  188. \smallskip
  189. \+\op void       print {char\ space = '\ '}
  190.                             {Calls $L$.print($cout$, $space$) to print $L$ on}
  191. \+\nop                      {the standard output stream $cout$.}
  192. \smallskip
  193. \+\op void       print {string\ s,\ char\ space = '\ '}    {} 
  194. \+\nop                      {As above, but uses string $s$ as a header.}
  195.  
  196.  
  197.  
  198. \medskip
  199. {\bf d) Iterators }
  200. \medskip
  201. Each list $L$ has a special item called the iterator of $L$. There 
  202. are operations to read the current value or the contents of this iterator,
  203. to move it (setting it to its successor or predecessor) and to test whether 
  204. the end (head or tail) of the list is reached. If the iterator contains a 
  205. $list\_item \neq nil$ we call this item the position of the iterator. 
  206. Iterators are used to implement iteration statements on lists.
  207. \bigskip
  208. \+\op void       set\_iterator {list\_item\ it}          
  209.                             {assigns item $it$ to the iterator}
  210. \+\nop                      {\precond $it$ is in $L$ or $it$ = nil. }
  211. \smallskip
  212. \+\op void       init\_iterator {}         
  213.                             {assigns nil to the iterator}
  214. \smallskip
  215. \+\op list\_item get\_iterator {}          
  216.                             {returns the current value of the iterator}
  217. \smallskip
  218. \+\op list\_item move\_iterator {direction\ dir=forward}    {}
  219. \+\nop                      {moves the iterator to its successor (predecessor)}
  220. \+\nop                      {if $dir=forward$ ($backward$) and to the first}
  221. \+\nop                      {(last) item if it is undefined (= nil), returns}
  222. \+\nop                      {the iterator.}
  223. \smallskip
  224. \+\op bool       current\_element {E\&\ x} 
  225.                        {if the iterator is defined ($\neq$ nil) its contents is}
  226. \+\nop                 {assigned to $x$ and true is returned else false}
  227. \+\nop                 {is returned}
  228. \smallskip
  229. \+\op bool       next\_element {E\&\ x} 
  230.                             { $L$.move\_iterator($forward$) $+$}
  231. \+\nop                      { return $L$.current\_element($x$) }
  232. \smallskip
  233. \+\op bool       prev\_element {E\&\ x} 
  234.                             { $L$.move\_iterator($backward$) $+$}
  235. \+\nop                      { return $L$.current\_element($x$)  }
  236.  
  237.  
  238. \bigskip
  239. {\bf e) Operators}
  240. \medskip
  241. \+\opa E\&  {list\_item\ it}  
  242.                            {returns a reference to the contents of $it$.}
  243. \medskip
  244. \+\opb list\<E\>\& =  L_1   
  245.                            {The assignment operator makes $L$ a copy of}
  246. \+\nop                     {list $L_1$. More precisely if $L_1$ is the sequence}
  247. \+\nop                     {of items $x_1, x_2, \dots x_n$ then $L$ is made a}
  248. \+\nop                     {sequence of items $y_1, y_2, \dots y_n$ with}
  249. \+\nop                     {$L[y_i] = L_1[x_i]$ for $1 \le i \le n$.}
  250.  
  251. \bigskip
  252. {\bf 4. Iteration}
  253.  
  254. {\bf forall\_items}($it,L$)       
  255. $\{$ ``the items of $L$ are successively assigned to $it$'' $\}$
  256.  
  257. {\bf forall}($x,L$)       
  258. $\{$ ``the elements of $L$ are successively assigned to $x$'' $\}$
  259.  
  260. \bigskip
  261. {\bf 5. Implementation}
  262.  
  263. The data type list is realized by doubly linked linear lists. All operations
  264. take constant time except for the following operations. Search and rank take 
  265. linear time $O(n)$, bucket\_sort takes time $O(n + j - i)$ and sort takes time 
  266. $O(n\cdot c\cdot\log n$) where $c$ is the time complexity of the compare
  267. function. $n$ is always the current length of the list.
  268.  
  269.